\documentclass[fleqn,english]{article}               % final
\usepackage[T1]{fontenc}
\usepackage{babel}
\usepackage{url}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[margin=1.5in]{geometry}
\usepackage{multirow}

\title{Algorithmics \\ Programming exercise}

\author{
  Christian Hafner
  \thanks{christianhafner@gmail.com}
  \and
  Kevin Streicher
  \thanks{kevin.streicher.at@gmail.com}
}

\begin{document}

\maketitle

\section{Notation}

Given is a weighted undirected graph $G'=(V,E',f')$ with $V=\{v_0,v_1,\ldots,v_{n-1}\}$ and $f':E' \rightarrow \mathbb{N}_0$. $v_0$ is a virtual node which is adjacent to all other nodes via edges of weight 0. The goal is to find a $k$-MST of $\{v_1,\ldots,v_{n-1}\}$, i.e.\ a subgraph of $G'$ which is a tree of $k$ nodes and has maximum weight.

We transform $G'$ into a directed graph $G = (V,E,f)$. Every edge $v_0w$ is replaced by a directed edge $(v_0,w)$. Every edge $vw$ not incident to $v_0$ is replaced by two directed edges $(v,w)$ and $(w,v)$. Every directed edge is assigned the weight of its corresponding undirected edge. The symbols $\Gamma^+$ and $\Gamma^-$ are used with respect to $G$.

The task of finding a $k$-MST in $G'$ is equivalent to finding an arborescence in $G$ by selecting a subset of $E$.
\section{Arborescence}
There are several rules which define our arborescence. These rules are part of the MTZ, SCF and MCF implementations.

\begin{enumerate}
\item We select exactly one of the outgoing edges of $v_0$, thereby choosing a unique root:
\[ \sum_{v \in V_1} e_{0v} = 1. \]

\item A node can have at most one incoming edge. This constraint forbids nodes with more than one parent:
\[ \forall v \in V_1: \sum_{u \in \Gamma^-(v)} e_{uv} \leq 1. \]

 \item The last constraint ensures that the tree has exactly $k$ nodes by using the property of trees $|V| = |E|+1$:
\[ \sum_{(v,w) \in E} e_{vw} = k. \]
This includes the $k-1$ edges of the $k$-MST and the virtual edge from $v_0$ to the root of the $k$-MST.

\end{enumerate}

\section{Miller-Tucker-Zemlin}

We introduce a Boolean variable $e_{vw}$ for each edge $(v,w) \in E$. $e_{vw}$ is 1 if the edge $e_{vw}$ is selected to be part of the $k$-MST and 0 otherwise.

Additionally we define a real-valued order variable $o_v$ for each node $v \in \{v_1, \ldots, v_{n-1}\}$. The virtual node $v_0$ has a predefined constant order of $o_0 := 0$. $o_v$ is a lower bound on the distance of $v$ from $v_0$ in the $k$-MST.

Below is a list of all linear constraints used to model the $k$-MST problem. The set $\{v_1, \ldots, v_{n-1}\}$ is abbreviated by $V_1$.

\begin{enumerate}
\item The maximum possible distance from $v_0$ is $k$ in case of the $k$-MST being a linear list:
\[ \forall v \in V_1: 1 \leq o_v \leq k. \]

\item A node other than $v_0$ can only have outgoing edges if it has an incoming edge. This constraint forbids acyclic structures that are not connected to $v_0$:
\[ \forall v \in V_1: M \sum_{u \in \Gamma^-(v)} e_{uv} \geq \sum_{w \in \Gamma^+(v)} e_{vw}. \]
The most restrictive value possible for $M$ is $k-1$, because a node in $V_1$ can have at most $k-1$ outgoing edges.

\item To forbid cycles that are not connected to $v_0$ we enforce an ordering of all nodes in the $k$-MST:
\[ \forall (v,w) \in E: o_v + e_{vw} \leq o_w + M(1-e_{vw}). \]
If an edge is unselected, the constraint is non-restrictive. Otherwise, the order of the start vertex and the order of the end vertex must differ by at least 1. The most restrictive value possible for $M$ is $\lceil k/2 \rceil$. This value is reached if the $k$-MST is a linear list and there is an unselected node that is adjacent both to the root and to the leaf.

Node that $o_0$ is not a variable but the constant 0. Also, the term $M(1-e_{vw})$ can be omitted for the outgoing edges of $v_0$. The above constraints ensure that only subtrees of $G$ are feasible solutions.
\end{enumerate}

\section{Single-commodity flow}
We introduce a Boolean variable $e_{vw}$ for each edge $(v,w) \in E$. $e_{vw}$ is 1 if the $(v,w)$ is selected to be part of the $k$-MST and 0 otherwise.

Additionally we define a real-valued flow variable $f_{vw}$ for each edge $(v,w) \in E, v \neq v_0$. It represents the amount of flow on edge $(v,w)$. The source $v_0$ sends out a flow of $k$ units. Each node that is reached by an incoming edge consumes one unit of flow.

The following constraints are used to model the $k$-MST problem in our arborescence formulation:

\begin{enumerate}
\item The flow on unselected edges is zero. The flow on any selected non-virtual edge is between one and $k-1$. 
\[ \forall (v,w) \in E, v \neq v_0: e_{vw} \leq f_{vw} \leq (k-1)e_{vw}. \]
The root consumes one unit of flow and thus sends at most $k-1$ units along any outgoing edge.

\item If a node is in the $k$-MST, it consumes exactly one unit of flow. Otherwise it consumes zero units of flow. This can be expressed as follows:
\[ \forall v \in V_1: ke_{v_0v} + \sum_{\substack{u \in \Gamma^-(v) \\ u \neq v_0}} f_{uv} - \sum_{w \in \Gamma^+(w)} f_{vw} = \sum_{u \in \Gamma^-(v)} e_{uv}. \]
This way a node conserves flow if it has no incoming edge and it consumes one unit of flow if it has an incoming edge. Note that $ke_{v_0v}$ is part of the inflow of $v$. It represents the $k$ units of flow that the virtual source sends along its only outgoing edge.
\end{enumerate}

\section{Multi-commodity flow}
In a multi-commodity flow model flow variables of different type are used. The artificial source node $v_0$ sends out $k$ different commodities designated for $k$ target nodes. Each commodity $c_i, i > 0$ needs to reach node $v_i$.

We have to track the flow of each commodity $c$ on each edge $(v,w)$, which results in many more constraints and variables compared to the SCF formulation. The huge amount of constraints and variables makes this formulation much slower. Multi-commodity flow formulations should be used for models which simply cannot be described by MTZ or SCF like network flows with costs associated to the type and the amount.

A real-valued flow variable $f_{cvw}$ for each edge $(v,w) \in E,v \neq v_0$ and every commodity $c$ is defined. The set $\{c_1,c_2,...,c_{n-1}\}$ is abbreviated with C. Each node $v_i$ beside the artificial source is associated with the commodity $c_i$. The flow variable $f_{cvw}$ describes the amount of commodity $c$ which is transferred from node $v$ to $w$. Each node, that is part of the $k$-MST, must consume exactly 1 unit of his designated commodity and may not use up any other resources.
\begin{enumerate}
\item Node $v_0$ sends out a flow of k.
\[\sum_{c \in C}\sum_{w \in \Gamma^+(v_0)} f_{cv_0w} = k.\]

\item The flow of every commodity $c$ on every edge $(v,w)$ needs to satisfy $0 \leq f_{cvw} \leq e_{vw}$. This ensures that there is no flow on edges which are not selected and no negative flow can appear.

\[\forall c \in C,\forall (v,w) \in E: 0 \le f_{cvw} \le e_{vw}. \]

\item The incoming flow for each node needs to flow out unless it is flow of the commodity designated for it. For commodity $c_i$ and node $v_i$, the difference of inflow and outflow needs to be equal to the number of selected incoming edges. With the arborescence constraint of a maximum of one incoming edge per node, this number is 0 for unselected nodes and 1 for selected nodes.
% With the arborescence constraint of a maximum of one incoming edge per node, this constraint is disabled for not selected nodes and results in a difference of $1$ for $c_i$ on selected nodes.

\[\forall v_i \in V_1,\forall c_j \in C, i \neq j: \sum_{u \in \Gamma^-(v_i)} f_{c_j uv_i} - \sum_{w \in \Gamma^+(v_i)} f_{c_j v_iw} = 0. \]
\[\forall v_i \in V_1: \sum_{u \in \Gamma^-(v_i)} f_{c_iuv_i} - \sum_{w \in \Gamma^+(v_i)} f_{c_iv_iw} = \sum_{u \in \Gamma^-(v_i)} e_{uv_i}. \]

\end{enumerate}
\section{Results}
% Please remember to add \use{multirow} to your document preamble in order to suppor multirow cells
\begin{table}[h]
\begin{tabular}{|c|r|r|r|r|r|r|r|r|}
\hline
\multicolumn{1}{|l}{}        & \multicolumn{1}{|l}{}  & \multicolumn{1}{|l}{}              & \multicolumn{2}{|c}{MTZ}                                       & \multicolumn{2}{|c}{SCF}                                       & \multicolumn{2}{|c|}{MCF}                                       \\ \hline
\multicolumn{1}{|l}{Instance} & \multicolumn{1}{|l}{k} & \multicolumn{1}{|l}{Opt. Value} & \multicolumn{1}{|l}{time} & \multicolumn{1}{|l}{BnB nodes} & \multicolumn{1}{|l}{time} & \multicolumn{1}{|l}{BnB nodes} & \multicolumn{1}{|l}{time} & \multicolumn{1}{|l|}{BnB nodes} \\ \hline \hline
\multirow{2}{*}{1}           & 2                      & 46                                 & 0                             & 0                              & 0.015                         & 0                              & 0.046                         & 0                               \\ \cline{2-9} 
                             & 5                      & 477                                & 0.015                         & 0                              & 0.046                         & 0                              & 0.046                         & 0                               \\ \hline
\multirow{2}{*}{2}           & 4                      & 373                                & 0.093                         & 0                              & 0.015                         & 0                              & 0.218                         & 0                               \\ \cline{2-9} 
                             & 10                     & 1390                               & 0.125                         & 535                            & 0.124                         & 97                             & 0.125                         & 0                               \\ \hline
\multirow{2}{*}{3}           & 10                     & 725                                & 0.171                         & 286                            & 0.202                         & 14                             & 0.656                         & 0                               \\ \cline{2-9} 
                             & 25                     & 3074                               & 0.859                         & 1413                           & 0.171                         & 0                              & 0.781                         & 0                               \\ \hline
\multirow{2}{*}{4}           & 14                     & 909                                & 0.406                         & 132                            & 0.436                         & 281                            & 3.281                         & 110                             \\ \cline{2-9} 
                             & 35                     & 3292                               & 0.671                         & 598                            & 0.639                         & 294                            & 5.312                         & 3                               \\ \hline
\multirow{2}{*}{5}           & 20                     & 1235                               & 0.421                         & 367                            & 0.452                         & 151                            & 5.906                         & 13                              \\ \cline{2-9} 
                             & 50                     & 4898                               & 4.109                         & 4898                           & 0.951                         & 159                            & 5.375                        & 0                               \\ \hline
\multirow{2}{*}{6}           & 40                     & 2068                               & 16.27                         & 15521                          & 12.63                         & 2644                           & 203.859                        & 208                             \\ \cline{2-9} 
                             & 100                    & 6705                               & 55.80                         & 21140                          & 11.66                         & 1150                           & 545.78                        & 7                               \\ \hline
\multirow{2}{*}{7}           & 60                     & 1335                               & 16.25                         & 834                            & 17.08                         & 722                            & 272.315                      & 0                               \\ \cline{2-9} 
                             & 150                    & 4534                               & 38.50                         & 3866                           & 41.01                         & 2216                           & 4723.24                       & 0                                 \\ \hline
\multirow{2}{*}{8}           & 80                     & 1620                               & 15.15                         & 691                            & 71.33                         & 920                            & 1675.68                              & 0                                \\ \cline{2-9} 
\multicolumn{1}{|l|}{}       & 200                    & 5787                               & 390.56                           & 43767                          & 77.20                         & 516                            & -                             & -                               \\ \hline
\end{tabular}
\end{table}
\section{Discussion}
MCF was much slower for instances 4 and up, which is explained by the number of additional constraints and variables for the different commodities. We have also experienced unexpected changes in running time when making the following modifications to our constraints:
\begin{itemize}
\item The constraint $\sum_{(v,w) \in E} e_{vw} = k$ is not necessary for the correctness of MCF. Changing the $=$ sign to $\leq$ led to a speedup of factor 2 for some of the smaller instances, although it is a relaxation.
\item Changing only the order in which variables are added to a constraint, but not changing the term in a mathematical sense, led to a slowdown of factor 10 for one instance.
\end{itemize}
Also we have seen speedups of up to factor 10 by using a different order of input variables and equivalent constraints in CPLEX.

\end{document}